home *** CD-ROM | disk | FTP | other *** search
- Path: ix.netcom.com!news
- From: Norman Bullen <nbullen@ix.netcom.com>
- Newsgroups: comp.lang.c
- Subject: Re: need psudeo code for binary search
- Date: Sat, 02 Mar 1996 08:30:30 -0800
- Organization: Black Cat Associates
- Message-ID: <313877A6.4047@ix.netcom.com>
- References: <Pine.SOL.3.91.960229154211.27358B-100000@obelix> <4h77mu$qtb@news1.cle.ab.com>
- NNTP-Posting-Host: ple-ca9-22.ix.netcom.com
- Mime-Version: 1.0
- Content-Type: text/plain; charset=us-ascii
- Content-Transfer-Encoding: 7bit
- X-NETCOM-Date: Sat Mar 02 10:42:12 AM CST 1996
- X-Mailer: Mozilla 2.0 (Win16; I)
-
- Donald-Anthony C. Phillips wrote:
- >
- > The binary search algorithm works as follows:
- > 1) Remember the structure must already be sorted.
- > 2) It works better as a recursive function
- It actually works better when written as a loop because it will use much
- less stack space.
-
- int BinarySearch(char *pstrTarget, char *pstrTable[], int tableSize)
- { int comp, hi, lo, look;
-
- hi = tableSize-1; lo = 0;
- while (hi>=lo) {
- look = (hi+lo)/2;
- comp = strcmp(pstrTarget, pstrTable[look]);
- if (comp==0) return look; /* Found it! */
- if (comp>0)
- lo = look+1;
- else
- hi = look-1;
- }
- return 0; /* Didn't find it. */
- }
-
- I've assumed that you meant to search an array of strings, not an array
- of chars.
-
- The idea of a binary search is to split the search area into two (more or
- less) equal parts and look at the item that falls in the middle. If its
- the one you're looking for you are done. Otherwise, if the item you are
- looking for is greater that the one you just looked at you know that it
- will be in the upper of the two parts. If less, in the lower of the two
- parts. If its not there at all, eventually the range of items collapses
- and you drop out of the loop.
-
- (You may have to play with that piece of code a little; I think its right
- but I did not attempt any sort of testing.)
-